#include "rbtree.hpp"
#include <algorithm>

// class KeyOfT
// {
// public:
//     int operator()(int key)
//     {
//         return key;
//     }
// };
// int main()
// {
//     STL::RBTree<int, int, KeyOfT> rbtree;
//     rbtree.insert(3);
//     rbtree.insert(4);
//     rbtree.insert(5);
//     rbtree.inorder();

//     return 0;
// }

// #include <iostream>

// class KeyOfT
// {
// public:
//     int operator()(int key)
//     {
//         return key;
//     }
// };

// int main()
// {
//     STL::RBTree<int, int, KeyOfT> rbtree;

//     // 插入测试
//     std::cout << "插入元素: ";
//     rbtree.insert(3);
//     rbtree.insert(4);
//     rbtree.insert(5);
//     rbtree.insert(1);
//     rbtree.insert(2);
//     rbtree.insert(6);

//     rbtree.inorder();  // 应该输出有序序列

//     return 0;
// }

// #include <string>

// class StringKeyOfT
// {
// public:
//     std::string operator()(const std::pair<std::string, int>& data)
//     {
//         return data.first;
//     }
// };

// int main()
// {
//     STL::RBTree<std::string, std::pair<std::string, int>, StringKeyOfT> dict;

//     // 插入单词和频率
//     dict.insert({"apple", 5});
//     dict.insert({"banana", 3});
//     dict.insert({"cherry", 7});
//     dict.insert({"date", 2});
//     dict.insert({"elderberry", 1});

//     dict.inorder();  // 按字典序输出

//     return 0;
// }

// #include <vector>
// #include <random>
// #include <algorithm>

// class KeyOfT
// {
// public:
//     int operator()(int key)
//     {
//         return key;
//     }
// };

// template <class T>
// class Compare
// {
// public:
//     bool operator()(const T &first, const T &second)
//     {
//         return first < second;
//     }
// };

// int main()
// {
//     STL::RBTree<int, int, KeyOfT, std::less<int>> rbtree;

//     // 生成随机数
//     std::vector<int> numbers;
//     for (int i = 1; i <= 1000; ++i)
//     {
//         numbers.push_back(i);
//     }

//     // 打乱顺序
//     std::random_device rd;
//     std::mt19937 g(rd());
//     std::shuffle(numbers.begin(), numbers.end(), g);

//     // 插入随机顺序的数字
//     std::cout << "插入1000个随机顺序的数字..." << std::endl;
//     for (int num : numbers)
//     {
//         rbtree.insert(num);
//     }

//     // std::cout << "最终红黑树的中序遍历结果:" << std::endl;
//     // rbtree.inorder(); // 应该输出1-1000的有序序列

//     std::cout << "是否符合红黑树标准：" << rbtree.check_redblack_tree() << std::endl;

//     // STL::RBTree<int, int, KeyOfT, std::less<int>>::iterator it = rbtree.begin();
//     // while (it != rbtree.end())
//     // {
//     //     std::cout << *it << " ";
//     //     ++it;
//     // }
//     // std::cout << std::endl;

//     STL::RBTree<int, int, KeyOfT, std::less<int>> rbtree2(rbtree);
//     STL::RBTree<int, int, KeyOfT, std::less<int>>::iterator it2 = rbtree2.begin();
//     std::cout << "是否符合红黑树标准：" << rbtree2.check_redblack_tree() << std::endl;
//     while (it2 != rbtree2.end())
//     {
//         std::cout << *it2 << " ";
//         ++it2;
//     }
//         // rbtree2.inorder(); // 应该输出1-1000的有序序列
//     std::cout << std::endl;
//     return 0;
// }

// #include "rbtree.hpp"
// #include <vector>
// #include <random>
// #include <algorithm>
// #include <cassert>
// #include <chrono>
// #include <unistd.h>

// class KeyOfT {
// public:
//     int operator()(int key) {
//         return key;
//     }
// };

// void test_basic_operations() {
//     std::cout << "=== 基础操作测试 ===" << std::endl;

//     STL::RBTree<int, int, KeyOfT, std::less<int>> tree;

//     // 测试插入
//     assert(tree.insert(5) == true);
//     assert(tree.insert(3) == true);
//     assert(tree.insert(7) == true);
//     assert(tree.insert(1) == true);
//     assert(tree.insert(4) == true);
//     assert(tree.insert(6) == true);
//     assert(tree.insert(8) == true);

//     // 测试重复插入
//     assert(tree.insert(5) == false);

//     std::cout << "插入测试通过" << std::endl;

//     // 测试中序遍历
//     std::cout << "中序遍历结果: ";
//     tree.inorder();

//     // 测试红黑树性质
//     assert(tree.check_redblack_tree() == true);
//     std::cout << "红黑树性质检查通过" << std::endl;
// }

// void test_iterator() {
//     std::cout << "\n=== 迭代器测试 ===" << std::endl;

//     STL::RBTree<int, int, KeyOfT, std::less<int>> tree;

//     // 插入测试数据
//     std::vector<int> data = {5, 3, 7, 1, 4, 6, 8, 2, 9, 0};
//     for (int num : data) {
//         tree.insert(num);
//     }

//     std::cout << "中序遍历: ";
//     tree.inorder();

//     std::cout << "迭代器遍历: ";
//     auto it = tree.begin();
//     while (it != tree.end()) {
//         std::cout << *it << " ";
//         ++it;
//     }
//     std::cout << std::endl;

//     // 测试反向迭代
//     std::cout << "反向迭代器遍历: ";
//     auto rit = tree.end();
//     --rit; // 移动到最后一个元素
//     while (true) {
//         // std::cout << *rit << " ";
//         // fflush(stdout);
//         // sleep(1);
//         if (rit == tree.begin()) break;
//         --rit;
//     }
//     std::cout << std::endl;
// }

// void test_copy_constructor() {
//     std::cout << "\n=== 拷贝构造函数测试 ===" << std::endl;

//     STL::RBTree<int, int, KeyOfT, std::less<int>> original;

//     // 插入一些数据
//     for (int i = 0; i < 10; ++i) {
//         original.insert(i * 2); // 插入偶数
//     }

//     std::cout << "原树中序遍历: ";
//     original.inorder();

//     // 测试拷贝构造
//     STL::RBTree<int, int, KeyOfT, std::less<int>> copy(original);

//     std::cout << "拷贝树中序遍历: ";
//     copy.inorder();

//     // 验证两棵树相同
//     auto it1 = original.begin();
//     auto it2 = copy.begin();

//     while (it1 != original.end() && it2 != copy.end()) {
//         assert(*it1 == *it2);
//         ++it1;
//         ++it2;
//     }
//     assert(it1 == original.end() && it2 == copy.end());

//     std::cout << "拷贝构造函数测试通过" << std::endl;
// }

// void test_large_dataset() {
//     std::cout << "\n=== 大数据集测试 ===" << std::endl;

//     STL::RBTree<int, int, KeyOfT, std::less<int>> tree;

//     // 生成1000个随机数
//     std::vector<int> numbers;
//     for (int i = 1; i <= 1000; ++i) {
//         numbers.push_back(i);
//     }

//     // 打乱顺序
//     std::random_device rd;
//     std::mt19937 g(rd());
//     std::shuffle(numbers.begin(), numbers.end(), g);

//     // 插入随机顺序的数字
//     std::cout << "插入1000个随机顺序的数字..." << std::endl;
//     for (int num : numbers) {
//         tree.insert(num);
//     }

//     // 验证排序
//     std::cout << "验证排序正确性..." << std::endl;
//     auto it = tree.begin();
//     int expected = 1;
//     int count = 0;
//     while (it != tree.end()) {
//         assert(*it == expected);
//         ++expected;
//         ++it;
//         ++count;
//     }
//     assert(count == 1000);

//     std::cout << "大数据集测试通过，元素数量: " << count << std::endl;
//     std::cout << "红黑树性质检查: " << tree.check_redblack_tree() << std::endl;
// }

// void test_string_keys() {
//     std::cout << "\n=== 字符串键测试 ===" << std::endl;

//     class StringKeyOfT {
//     public:
//         std::string operator()(const std::pair<std::string, int>& data) {
//             return data.first;
//         }
//     };

//     STL::RBTree<std::string, std::pair<std::string, int>, StringKeyOfT, std::less<std::string>> dict;

//     // 插入单词和频率
//     dict.insert({"apple", 5});
//     dict.insert({"banana", 3});
//     dict.insert({"cherry", 7});
//     dict.insert({"date", 2});
//     dict.insert({"elderberry", 1});

//     std::cout << "字典内容（按字母顺序）:" << std::endl;
//     auto it = dict.begin();
//     while (it != dict.end()) {
//         std::cout << it->first << ": " << it->second << std::endl;
//         ++it;
//     }

//     std::cout << "字符串键测试通过" << std::endl;
// }

// void test_edge_cases() {
//     std::cout << "\n=== 边界情况测试 ===" << std::endl;

//     STL::RBTree<int, int, KeyOfT, std::less<int>> tree;

//     // 测试空树
//     assert(tree.begin() == tree.end());
//     std::cout << "空树测试通过" << std::endl;

//     // 测试单个元素
//     tree.insert(42);
//     auto it = tree.begin();
//     assert(*it == 42);
//     ++it;
//     assert(it == tree.end());
//     std::cout << "单元素树测试通过" << std::endl;

//     // 测试重复插入
//     tree.insert(42); // 应该失败
//     it = tree.begin();
//     int count = 0;
//     while (it != tree.end()) {
//         ++count;
//         ++it;
//     }
//     assert(count == 1);
//     std::cout << "重复插入测试通过" << std::endl;
// }

// void performance_test() {
//     std::cout << "\n=== 性能测试 ===" << std::endl;

//     STL::RBTree<int, int, KeyOfT, std::less<int>> tree;

//     const int NUM_ELEMENTS = 10000;
//     std::vector<int> numbers;

//     for (int i = 0; i < NUM_ELEMENTS; ++i) {
//         numbers.push_back(i);
//     }

//     std::random_device rd;
//     std::mt19937 g(rd());
//     std::shuffle(numbers.begin(), numbers.end(), g);

//     auto start = std::chrono::high_resolution_clock::now();

//     for (int num : numbers) {
//         tree.insert(num);
//     }

//     auto end = std::chrono::high_resolution_clock::now();
//     auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

//     std::cout << "插入 " << NUM_ELEMENTS << " 个元素耗时: " << duration.count() << " ms" << std::endl;

//     // 验证所有元素都存在且有序
//     start = std::chrono::high_resolution_clock::now();

//     auto it = tree.begin();
//     int expected = 0;
//     while (it != tree.end()) {
//         assert(*it == expected);
//         ++expected;
//         ++it;
//     }
//     assert(expected == NUM_ELEMENTS);

//     end = std::chrono::high_resolution_clock::now();
//     duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

//     std::cout << "遍历验证 " << NUM_ELEMENTS << " 个元素耗时: " << duration.count() << " ms" << std::endl;
//     std::cout << "红黑树性质检查: " << tree.check_redblack_tree() << std::endl;
// }

// int main() {
//     try {
//         test_basic_operations();
//         test_iterator();
//         test_copy_constructor();
//         test_large_dataset();
//         test_string_keys();
//         test_edge_cases();
//         performance_test();

//         std::cout << "\n🎉 所有测试通过！" << std::endl;
//         return 0;
//     } catch (const std::exception& e) {
//         std::cerr << "测试失败: " << e.what() << std::endl;
//         return 1;
//     }
// }

template <class Key, class Val>
class KeyOfT
{
public:
    Key operator()(Val val)
    {
        return val.first;
    }
};
int main()
{
    STL::RBTree<int, std::pair<int, int>, KeyOfT<int, std::pair<int, int>>, std::less<int>> rbtree;
    rbtree.insert({1, 2});
    rbtree.insert({3, 3});
    rbtree.insert({2, 3});
    rbtree.insert({2, 3});
    rbtree.insert({5, 3});
    rbtree.insert({54, 3});
    rbtree.insert({24, 3});
    rbtree.inorder();
    return 0;
}